Metaobject Protocols.muse

   1 In Fall of 2006 I did a small project on Metaobject Protocols for my
   2 CS 331 class. Here lie my notes which may perhaps be useful to
   3 others. I hope to expand them into something more useful over time.
   4
   5 * Background
   6
   7 ** Object Protocols
   8
   9 An object protocol is a set of methods and specification of the
  10 interactions between the methods which provide some generic behavior
  11 (e.g. of a sequence) that are then implemented by classes which
  12 conform to the protocol (e.g. a vector or list). In most object
  13 systems a class contains both the methods which implement a protocol
  14 and the data used by the implementation. The intent is to emulate
  15 state machines which pass messages between each other.
  16
  17 ** CLOS Way of OO
  18
  19 The Common Lisp Object System (CLOS) is different. It separates
  20 the data and method concepts into classes and generics. A class
  21 contains data fields only, and a generic has methods specialized for
  22 certain types attached to it. This seems a bit weird at first, but is
  23 significantly more powerful as it encourages complete encapsulation
  24 through its use of classes primarily for method specialization rather
  25 than for state storage.
  26
  27
  28 *** Classes for scratch data and types
  29
  30 In CLOS classes store data in slots (which are the same as data
  31 members). Encapsulation is not provided; any bit of code can use
  32 =slot-value= to access or set the value of a slot. This may seem odd at
  33 first, but encapsulation is of questionable importance as the slots
  34 are meant only to be used by the protocol defined around the class.
  35
  36 Classes are defined with defclass
  37
  38 <src lang="lisp">
  39 (defclass name (superclasses ...)
  40   ((slot-name :accessor slot-accessor ...)
  41    ...)
  42   (class-options ...))
  43
  44 (defclass example ()
  45   ((foo :accessor foo-of :initform 5)))
  46
  47 (defclass example-child (example)
  48   ((bar :accessor bar-of :initform (list 1 2 3))))
  49 </src>
  50
  51 Slot defintions have several option; the above example shows only the
  52 =:accessor= and =:initform= options which are the most commonly
  53 used. =:accessor= generates an accessor for the slot (e.g. if you have
  54 an instance of =example= you can =(setf (foo-of some-example-instance) 'some-value)= to set and =(foo-of some-example-instance)= to access the
  55 value). =:initform= provides a default initial value for the slot as a
  56 symbolic expression to be evaluated when an instance is created.
  57
  58 *** Generics with methods that implement protocols
  59
  60 Generics are like normal functions in Lisp, but they only provide a
  61 lambda list (parameter list). Methods are added to the generic which
  62 specialize on the types of their parameters, and provide the actual
  63 implementation. This allows for rich layered protocols to be developed
  64 which can enable selective modification of individual facets with
  65 minimal code.
  66
  67 <src lang="lisp">
  68 (defgeneric generic (parameters ...)
  69   (options) ...)
  70
  71 (defmethod generic-name ((parameter type) parameter ...)
  72   "documentation string"
  73   body)
  74
  75 (defgeneric foo (bar baz quux)
  76   (:documentation "Process the baz with the quux capacitor to make the
  77 foo widget fly into the sky at warp speed"))
  78
  79 (defmethod foo ((bar example) baz (quux capacitor))
  80   (launch bar (process-with quux baz)))
  81 </src>
  82
  83 A method lambda list differs from a normal lambda list only in that it
  84 can specify the type of the parameter using the notation =(name type)=.
  85 Note also that methods can specialize on the types of every
  86 argument and not just the first one. This is quite powerful for
  87 reasons outside of the scope of this presentation.
  88
  89 * Limitations of Default Language Behavior
  90
  91 The behavior of a language is a compromise between many competing
  92 issues that attempts to be as generally useful as possible, and most
  93 applications will have no issue with the default behavior. There are,
  94 however, certain applications that could be cleanly written with minor
  95 modifications to the behavior of the language, but would be impossible
  96 or quite difficult to write otherwise.
  97
  98 ** Slot Storage
  99
 100 Most languages choose to preallocate storage for all of the slots of
 101 an instance. Imagine a contact database that stored information about
 102 people as slots of the class. There may be dozens of slots, but often
 103 many of them will be left blank. If slot storage is preallocated much
 104 memory will be wasted and the system may not be able to fit into the
 105 memory of the hardware it must run on (perhaps for financial reasons,
 106 huge datasets, etc.).
 107
 108 To save memory the author of the contact database must implement his
 109 own system to store properties and allocate them lazily. This
 110 represents a fair bit of effort, and would implement a system that
 111 differed from the existing slot system of classes only in the method
 112 of data storage.
 113
 114 It would be useful if there were a way to customize instance
 115 allocation. The customizations would be minor and require overriding
 116 only the initial allocation behavior and the behavior of the first
 117 assignment to the slot. It is a a trivial problem in a language that
 118 allows customization of these.
 119
 120 ** Design Patterns
 121
 122 Design Patterns are generalized versions of common patterns found in
 123 programs. Many of them are merely methods to get around deficiencies
 124 in the language, and can be quite messy to implement in some
 125 languages.
 126
 127 * Metasoftware
 128
 129 Some types of programs could be written easily if the language were
 130 customizable, but are nearly impossible to write when it is not.
 131
 132 ** Runtime Generated Classes
 133
 134 Say you wanted to write a video game where players could create their
 135 own objects, attach behaviors to the objects, and perhaps mix
 136 different objects together to create new ones. When you abstract the
 137 problem this looks just like an object system!  Wouldn't it be nice if
 138 your program could create new objects and methods on the fly portably?
 139
 140 ** Object Inspection
 141
 142 Imagine if you were developing a complicated program with many
 143 different objects that interacted in fairly complex ways. A tool to
 144 inspect the structure of objects while debugging would be quite
 145 useful, but in a traditional language would be impossible to implement
 146 portably. This could force you to purchase a certain compiler
 147 implementation which provided one, and even then would more than
 148 likely not be customizable.
 149
 150 This problem can be generalized to apply to most debugging tools; it
 151 would be useful to write such tools portably because users of the
 152 *language* and not the *compiler* need to debug software. Sharing
 153 infrastructure would result in better tools (more developers), and
 154 save man-years of wasted effort that comes with having to rewrite
 155 non-portable functionality from scratch multiple times.
 156
 157 * Metaobject Protocols
 158
 159 ** Limited/Generalized Internals of the Implementation
 160
 161 A Metaobject protocol is a generalized and limited subset of the
 162 underlying implementation of the language. It is generalized and
 163 limited in scope to allow for multiple implementation strategies;
 164 this, along with careful design, is essential because programming
 165 language research is ever advancing and new techniques for creating
 166 more reliable and faster implementations are still being discovered.
 167
 168 This subset of the implementation is exported as a set of methods on
 169 metaobjects. Thus the system is implemented in itself. The system can
 170 then be customized using the extension and overriding features of the
 171 system.
 172
 173 ** Classes of MOPs
 174
 175 *** Reflective
 176
 177 A reflective MOP provides a functional/procedural interface to
 178 information about the system. It exposes class relationships, the
 179 methods are attached to a generic, etc. A reflective MOP often
 180 provides some functionality for creating new classes at runtime.
 181
 182 **** Example: Object Inspector
 183
 184 **** Example: Runtime Generated Classes and Methods
 185
 186 *** Intercessory
 187
 188 Intercessory MOPs allow the user to customize language behavior by
 189 implementing methods which override certain aspects of the language
 190 behavior. This class of MOPs are what make MOPs especially
 191 powerful. No longer must a problem be restructured to fit the
 192 implementation language; the underyling language can be reshaped to
 193 fit the task at hand, and obfuscation of the intended structure of the
 194 application can be avoided.
 195
 196 **** Example: Lazily Allocated Slots
 197
 198 **** Example: Observer Design Pattern
 199
 200 ** Violation of Encapsulation?
 201
 202 A MOP may seem like a violation of encapsulation by revealing some
 203 implementation details, but in reality a well designed protocol does
 204 not reveal anything which was not already exposed. Implementation
 205 decisions affect users, and some of these details do leak through to
 206 higher levels (e.g. the memory layout of slots). Implicit in the
 207 protocol specification are these implementation details, and the MOP
 208 merely makes this limited subset available for customization.
 209
 210 A MOP makes it possible to customize certain implementation decisions
 211 that do not **radically** alter the behavior of the base language. The
 212 conceptual vocabulary of the system retains its meaning, and so code
 213 written in one dialect can interact with code written in another
 214 without knowing that they speak different ones.
 215
 216 * MOP Design Principles
 217
 218 ** Layered Protocol
 219
 220 A layered protocol design is good for both meta and normal object
 221 protocols, and enables a combinatorial explosion of customizations to
 222 the protocol.
 223
 224 *** Top level **must** call lower level functions
 225
 226 The top level methods of a layered metaobject protocol are required to
 227 call certain methods to perform some tasks. This both makes it easier
 228 to customize the top level methods (which perform very broad tasks) by
 229 providing some pieces of them for the programmer, and allows more
 230 customization to be done by opening up the replacement of lower level
 231 functions as a way to alter a small detail of the high level behavior.
 232
 233 *** Lower level methods are easier to customize
 234
 235 The lower level methods of a MOP are limited in scope and can be
 236 implemented easily. Often the changes to language behavior that are
 237 wanted are very small, and having methods that perform simple tasks
 238 which are often customized reduces the effort required to extend the
 239 system.
 240
 241 ** Functional Where Possible
 242
 243 Functional protocols are preferred for MOPs (and object protocol in
 244 general). Functional protocols open up several optimizations for the
 245 implementation without burdening the user of the protocol.
 246
 247 *** Memoization
 248
 249 Memoization is the process of saving the results of a function call
 250 for future use. This avoids expensive recomputation of values which
 251 have not changed (recall that a true function will always return the
 252 same result when given the same arguments).
 253
 254 A functional MOP can be optimized easily by exploiting this property
 255 to memoize the return values of calls to expensive operations. A MOP
 256 must be be very fast to avoid making programs unusably slow, and
 257 memoization is able to give an appreciable speedup in many cases
 258 without an insignificant burden on memory usage.
 259
 260 **** Constant Shared Return Values
 261
 262 Disallowing the modification of values returned by protocol methods
 263 allows the implementation to return large data structures by reference
 264 to avoid expensive copying without having to do expensive data
 265 integrity checks.
 266
 267 *** Cleaner Code
 268
 269 ** Procedural Only Where Neccesary
 270
 271 Some operations like method invocation are inheretly stateful and so
 272 must use a procedural protocol. There is no benefit to be gained from
 273 using a functional protocol, and indeed an attempt would result in
 274 obtuse code that severely restricted the implementor. Do note that
 275 only a very small part of method invocation is stateful (the actual
 276 call), and most of it can be implemented functionally (e.g. computing
 277 the discriminating function).
 278
 279 * Examples
 280
 281 ** Object Inspector
 282
 283 A primitive portable object inspector is presented here.
 284
 285 <src lang="lisp">
 286 (defgeneric example-inspect (instance)
 287   (:documentation "Simple object inspector using CLOS MOP"))
 288
 289 (defmethod example-inspect ((instance t))
 290   (format t "Simple Object~% Value: ~S~%" instance))
 291
 292 (defmethod example-inspect ((instance standard-object))
 293   (let ((class (class-of instance)))
 294     (format t "Class: ~S, Superclasses: ~S~%"
 295             (class-name class)
 296             (mapcar #'class-name
 297                     (class-precedence-list class)))
 298     (let ((slot-names (mapcar #'slot-definition-name
 299                               (class-slots class))))
 300       (format t "Slots: ~%~{ ~S~%~}" slot-names)
 301       (inspect-loop slot-names instance #'example-inspect))))
 302
 303 (defun inspect-loop (slots instance inspector)
 304   (format t "Enter slot to inspect or :pop to go up one level: ")
 305   (finish-output)
 306   (let* ((slot (read))
 307          (found-slot (member slot slots)))
 308     (cond (found-slot
 309            (funcall inspector (slot-value instance slot))
 310            (funcall inspector instance))
 311           ((eq slot :pop) t)
 312           (t
 313            (format t "~S is invalid. Valid slot names: ~S~%"
 314                    slot
 315                    slots)
 316            (inspect-loop slots instance inspector)))))
 317 </src>
 318
 319 ** Observer Design Pattern
 320
 321 A simple implementation of the observer pattern is under 100 lines,
 322 and the user level code requires only a single line of code to make
 323 any existing class observable.
 324
 325 In a language lacking a MOP, implementing the observer pattern
 326 requires modifying every accessor of a class to explicitly invoke any
 327 observers, and neccesitates the addition of a mixin class to the class
 328 heirarchy. The fact that an object can be observed is a meta property
 329 of the class, and forcing it to be implemented at the application
 330 level dirties the inheritance heirarchy and adds uneccesary meta
 331 details to the program.
 332
 333 <src lang="lisp">
 334 ;;; This metaclass adds a slot to instances which use it, and so the
 335 ;;; system is defined in its own package to avoid name conflicts
 336 (defpackage :observer
 337   (:use :cl #+sbcl :sb-mop)
 338   (:export observable register-observer unregister-observer))
 339
 340 (in-package :observer)
 341
 342 ;;; Metaclass
 343 (defclass observable (standard-class)
 344   ()
 345   (:documentation "Metaclass for observable objects"))
 346
 347 (defmethod compute-slots ((class observable))
 348   "Add a slot for storing observers to observable instances"
 349   (cons (make-instance 'standard-effective-slot-definition
 350                        :name 'observers
 351                        :initform '(make-hash-table)
 352                        :initfunction #'(lambda () (make-hash-table)))
 353         (call-next-method)))
 354
 355 (defmethod validate-superclass ((class observable)
 356                                 (super standard-class))
 357   t)
 358
 359 (defun register-observer (instance slot-name key closure)
 360   (register-observer-with-class (class-of instance)
 361                                 instance
 362                                 slot-name
 363                                 key
 364                                 closure))
 365
 366 (defun unregister-observer (instance slot-name key)
 367   (unregister-observer-with-class (class-of instance)
 368                                   instance
 369                                   slot-name
 370                                   key))
 371
 372 (defun get-observers (instance slot-name)
 373   (get-observers-with-class (class-of instance)
 374                             instance
 375                             slot-name))
 376
 377 (defun add-observer-table (instance slot-name)
 378   (setf (gethash slot-name (slot-value instance
 379                                        'observers))
 380         (make-hash-table)))
 381
 382 (defgeneric register-observer-with-class (class instance slot-name key closure))
 383 (defgeneric unregister-observer-with-class (class
 384                                             instance
 385                                             slot-name
 386                                             key))
 387
 388 (defmethod register-observer-with-class ((class observable)
 389                                          instance
 390                                          slot-name
 391                                          key
 392                                          closure)
 393   (setf (gethash key
 394                  (or (gethash slot-name
 395                               (slot-value instance 'observers))
 396                      ;; Lazily add observer hash tables
 397                      (add-observer-table instance slot-name)))
 398         closure))
 399
 400 (defmethod unregister-observer-with-class ((class observable)
 401                                            instance
 402                                            slot-name
 403                                            key)
 404   (remhash key (gethash slot-name
 405                         (slot-value instance 'observers))))
 406
 407 (defmethod get-observers-with-class ((class observable)
 408                                      instance
 409                                      slot-name)
 410   (gethash slot-name (slot-value instance 'observers)))
 411
 412 (defmethod (setf slot-value-using-class) :before (new-value
 413                                                   (class observable)
 414                                                   instance
 415                                                   slot)
 416   (let ((slot-name (slot-definition-name slot)))
 417     (if (not (eq 'observers slot-name))
 418         (let ((observers
 419                (get-observers instance (slot-definition-name slot))))
 420           (if observers
 421               (maphash #'(lambda (key observer)
 422                            (funcall observer
 423                                     (if (slot-boundp instance slot-name)
 424                                         (slot-value instance slot-name)
 425                                       nil)
 426                                     new-value))
 427                        observers))))))
 428 </src>
 429
 430 ** Real World
 431 *** [[http://common-lisp.net/project/ucw/][UCW]] and [[http://common-lisp.net/project/bese/arnesi.html][Arnesi]]
 432
 433 Arnesi uses the CLOS MOP to implement methods which are transparantly
 434 rewritten into continuation passing style. This allows their execution
 435 to be suspended at certain points and resumed later. UCW builds on top
 436 of this to support a web framework where the statelessness of http is
 437 hidden from the user; displaying a page suspends the execution of the
 438 current continuation, and resumes it upon submission. The user level
 439 code is completely unaware of this.
 440
 441 *** [[http://clsql.b9.com][CLSQL]]
 442
 443 CLSQL uses the reflective part of the CLOS MOP to map Common Lisp data
 444 types into SQL types, and the intercessory protocol for slot
 445 allocation to map slots onto database columns or sql expressions (for
 446 implementing relational slots).
 447
 448 *** [[http://common-lisp.net/project/elephant/][Elephant]]
 449
 450 Elephant uses the CLOS MOP to transparantly store any class to disk
 451 and handle paging between the disk store and memory efficiently and
 452 with no user intervention.
 453
 454 * Sources & Further Reading
 455
 456 ** Sources
 457
 458 *** The Art of the Metaobject Protocol
 459 **** Kiczales, Gregor et al. MIT Press 1991
 460
 461 Highly recommended reading even if you plan to never implement a MOP
 462 or use the CLOS one. The design principles it recommends are quite
 463 useful.
 464
 465 *** [[http://www.lisp.org/mop/contents.html][CLOS MOP Specification]]
 466
 467 Specification of the MOP for CLOS defined in *The Art of the Metaobject Protocol*.
 468
 469 *** [[http://citeseer.ist.psu.edu/399658.html][Metaobject Protocols: Why We Want Them and What Else They Can Do]]
 470
 471 A short overview of MOP design principles followed by three example
 472 metaobject protocols for Scheme.
 473
 474 *** [[http://www2.parc.com/csl/groups/sda/projects/oi/towards-talk/transcript.html][Why Are Black Boxes so Hard to Reuse?]]
 475
 476 Transcription of a talk on the benefits of open implementations of
 477 software. It first discusses several problems that black box software
 478 implementations pose, and then presents existing solutions. It shows
 479 how the existing solutions are insufficient, and then provides
 480 metaobject protocols as a solution to most of the problems.
 481
 482 ** Further Reading
 483
 484 *** [[http://citeseer.ist.psu.edu/chiba95metaobject.html][A Metaobject Protocol for C++]]
 485
 486 Example of a purely compile time MOP. It implements the functionality
 487 of a code walker and something similar to the Lisp macro system.
 488
 489 *** [[http://www.parc.com/csl/groups/sda/publications/papers/Kiczales-TUT95/for-web.pdf][Open Implementations and Metaobject Protocols]]
 490
 491 It is a bit long, but it seems to follow a similar structure to AMOP
 492 in introducing MOPs and their usefulness. The pages are slides with
 493 notes, and so the 331 pages might not actually take that long to read.